[이코테-이진탐색]_부품 찾기
💯 solving-algo | March 29, 2021
문제 설명
N개의 부품 중에서 발주 된 부품(M)이 있는지 찾아 있으면 yes, 없다면 no를 출력하는 문제
My Solution
def binary_search(array, start, end):
answer = []
for target in range(len(request_product)):
while start <= end:
mid = (start + end) // 2
if array[mid] == request_product[target]:
answer.append("yes")
start = 0
end = have_product[-1]
break
elif array[mid] > request_product[target]:
end = mid - 1
else:
start = mid + 1
if array[mid] != request_product[target]:
answer.append("no")
start = 0
end = have_product[-1]
for i in answer:
print(i)
n = int(input())
have_product = list(map(int, input().split()))
have_product.sort()
m = int(input())
request_product = list(map(int, input().split()))
print(binary_search(have_product, 0, have_product[-1]))문제 풀이
- 내가 가지고 있는 물품(N)이 입력으로 주어졌을 때 정렬이 안 된 무작위의 숫자를 입력 받아 정렬을 하였다. 이진 탐색의 특성상 정렬이 필요하기 때문이다.
-
찾아야 하는 물품
target를 개별 인덱스로 두어for문 안에서 내가 가지고 있는 인덱스(mid) 와 이진 탐색으로 방식으로 접근하였다.- 있다면 answer 배열에 append, 없다면 break으로 탈출
- 또한 break문으로 탈출한 이후에 조건문을 설정하지 않는다면 무조건 no가 들어가는 현상이 발생했다. (당연한 결과인데, 어떻게 해결할지 난감해하고 있었다..)어차피 원하는 물건이(M)이 N에 없으면 알아서 탈출하는 조건문이 있어서(
while start <= end:),if array[mid] != request_product[target]:해당하는 값만no가 입력될 수 있도록 수정하였다.
이코테 풀이
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
end = mid - 1
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
start = mid + 1
return None
# n(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 공백으로 구분하여 입력
array = list(map(int, input().split()))
array.sort()
# m(손님이 요청한 부품 개수) 입력
m = int(input())
x = list(map(int, input().split()))
# 손님이 확인 요청한 전체 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
result = binary_search(array, i, 0, n - 1)
if result != None:
print('yes', end=' ')
else:
print('no', end=' ')이코테 풀이2(계수 정렬)
n = int(input())
array = [0] * 1000001
# 가겍에 있는 전체 부품 번호를 입력받아서 기록
for i in input().split():
array[int(i)] = 1
# M(손님이 확인 요청한 부품 개수)을 입력받기
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
if array[i] == 1:
print('yes', end=' ')
else:
print('no', end=' ')이코테 풀이3(집합 자료형 이용)
n = int(input())
# 가게에 있는 전체 부품 번호를 입력받아서 집합(set) 자료형에 기록
array = set(map(int, input().split()))
m = int(input())
x = list(map(int, input().split()))
for i in x:
# 해당 부품이 존재하는지 확인
if i in array:
print('yes', end=' ')
else:
print('no', end=' ')배운점
처음에 풀이를 진행하다가 “원하는 값들을 하나씩 확인했어야했나?” 라는 생각을 했었는데, 이코테 풀이를 보니 하나씩 풀이를 진행한 것을 확인할 수 있다. 또한 코드도 매우 간결하며, 쓰지 않은 변수가 없다(사실 하나 있다m). 본인은 n, m를 이용하지 못했다. 좀 더 많은 연습이 필요할 것 같다.
